import java.util.LinkedList;

/**
 * 单调递减队列
 * @author liuzhaoqiang
 */
public class MonotonicQueue {
    private LinkedList<Integer> queue = new LinkedList<>();

    /**
     * 获取队列头的数据
     * @return
     */
    public Integer peek() {
        return queue.peekFirst();
    }

    /**
     * 移除队列头的数据
     */
    public void poll() {
        queue.pollFirst();
    }

    @Override
    public String toString() {
        return queue.toString();
    }

    /**
     * 往队列尾部添加数据,需要保持单调递减
     * @param val
     */
    public void offer(int val) {
        while(!queue.isEmpty() && queue.peekLast() < val){
            queue.pollLast();
        }
        queue.offerLast(val);
    }

    public static void main(String[] args) {
        MonotonicQueue q = new MonotonicQueue();
        for (int i : new int[]{1,3,-1,-3,5,3,6,7}){
            q.offer(i);
            System.out.println(q);
        }
    }
}
